#include <iostream>
#include <chrono>
#include "AvlTree.h"
#include "SplayTree.h"

#define sector "------------------------------------"

using namespace std;

inline int rand_N(int testsize)
{
    return ((int)((float)rand() / (float)RAND_MAX * testsize));
}

template <typename T>
void PrintVector(const std::vector<T> &_data)
{
    for (T iter : _data)
    {
        cout << iter << ",";
    }
    cout << endl;
}

int main()
{
    cout << "Testing the result after sorting......" << endl;
    vector<int> test1, test2;
    int test_size = 100;
    cout << "The original vector: ";
    for (int i = 0; i < test_size; i++)
    {
        int tmp = rand() % 200;
        test1.push_back(tmp);
        test2.push_back(tmp);
        cout << tmp << ",";
    }
    cout << endl;
    cout << sector << endl;
    Avl_BST_sort<int>(test1);
    cout << "The vector after Avl_BST_sorting: ";
    PrintVector<int>(test1);

    Splay_BST_sort<int>(test2);
    cout << "The vector after Splay_BST_sorting: ";
    PrintVector<int>(test2);

    vector<int> v1, v2;
    int NUMS = 40000;

    for (int i = 0; i < NUMS; i++)
    {
        int size = rand_N(NUMS);
        v1.push_back(size);
        v2.push_back(size);
    }

    cout << sector << endl;
    cout << "Sorting a random vector with size " << NUMS << endl;
    cout << sector << endl;

    auto start = std::chrono::high_resolution_clock::now();
    Avl_BST_sort<int>(v1);
    auto end = std::chrono::high_resolution_clock::now();
    cout << "Avl_BST_sort takes " << (end - start).count() / float(1e9) << " seconds." << endl;

    //cout << sector << endl;

    start = std::chrono::high_resolution_clock::now();
    Splay_BST_sort<int>(v2);
    end = std::chrono::high_resolution_clock::now();
    cout << "Splay_BST_sort takes " << (end - start).count() / float(1e9) << " seconds." << endl;

    // double Avl_Total = 0, Splay_Total = 0;
    // for (int i = 0; i < 1000; i++)
    // {
    //     v1.clear();
    //     v2.clear();
    //     for (int i = 0; i < NUMS; i++)
    //     {
    //         int size = rand_N(NUMS);
    //         v1.push_back(size);
    //         v2.push_back(size);
    //     }

    //     start = std::chrono::high_resolution_clock::now();
    //     Avl_BST_sort<int>(v1);
    //     end = std::chrono::high_resolution_clock::now();
    //     Avl_Total += (end - start).count() / float(1e9);

    //     start = std::chrono::high_resolution_clock::now();
    //     Splay_BST_sort<int>(v2);
    //     end = std::chrono::high_resolution_clock::now();
    //     Splay_Total += (end - start).count() / float(1e9);
    // }

    // cout << sector << endl;
    // cout << "1000 times Avl_BST_sort take average time : " << Avl_Total / double(1000) << endl;
    // cout << "1000 times Splay_BST_sort take average time : " << Splay_Total / double(1000) << endl;
}
